#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "stack.h"
#include "binary_tree.h"



static binary_tree_node_s * binary_tree_node_create(int data)
{
	binary_tree_node_s *tree_node = (binary_tree_node_s *)malloc(sizeof(binary_tree_node_s));

	if  (tree_node != NULL) {
		tree_node->data = data;
		tree_node->left = NULL;
		tree_node->right = NULL;
	}
	return tree_node;
}

binary_tree_s *binary_tree_create(void)
{
	binary_tree_s *tree = (binary_tree_s*)malloc(sizeof(binary_tree_s));

	if (tree != NULL) {
		tree->root = NULL;
	}
	return tree;
}
void binary_tree_destory(binary_tree_s *tree)
{
	
}
int binary_tree_get_length(binary_tree_s *tree)
{
	return 0;
}
ret_e  binary_tree_add_data(binary_tree_s *tree,int data)
{
	binary_tree_node_s *node = NULL;
	binary_tree_node_s *connect_node = NULL;
		
	if (tree == NULL) {
		return RET_PRA;
	}
	node = tree->root;
	while (node != NULL) {
		connect_node  = node;
		if (data <=  node->data) {
			node = node->left;
		} else {
			node = node->right;
		}
	}
	node = binary_tree_node_create(data);
	if (node == NULL) {
		return RET_MEM;
	}
	if (connect_node == NULL) {
		tree->root = node; 
	} else {
		if (data <= connect_node->data) {
			connect_node->left = node;
		} else {
			connect_node->right = node;
		}
	}
	return RET_OK;
}

ret_e binary_tree_for_loop(binary_tree_node_s *root,loop_func loop_fun,void *context)
{
	if (root == NULL || loop_fun == NULL) {
		return RET_PRA;
	}
	binary_tree_for_loop(root->left, loop_fun,context);
	if (loop_fun(root->data,context) == RET_END) {
		return RET_OK;
	}
	binary_tree_for_loop(root->right, loop_fun,context);
	return RET_OK;
}
void binary_tree_display(binary_tree_node_s *root)     
{
	if (root != NULL) {
		printf("%d ",root->data);
		if (root->left != NULL) {
		    putchar('(');
		    binary_tree_display(root->left);
			if (root->right == NULL) {
				putchar(')');
			}
		}
		if (root->right != NULL) {
		  	if (root->left == NULL) {
				putchar('(');
			}
		    putchar(',');
		    binary_tree_display(root->right);
		    putchar(')');
		}
	}
}

ret_e binary_tree_print(binary_tree_s *tree,loop_func loop_fun)
{
	ret_e ret;

	
	if (tree == NULL) {
		return RET_PRA;
	}
	putchar('\n');
	ret = binary_tree_for_loop(tree->root,loop_fun,NULL);
	putchar('\n');
	
	return ret;
}
static ret_e binary_tree_for_loop_inter(binary_tree_node_s *root,ret_e (*loop_fun)(void *node,void *conext),void *context)
{
	if (root == NULL || loop_fun == NULL) {
		return RET_PRA;
	}
	binary_tree_for_loop_inter(root->left, loop_fun,context);
	if (loop_fun(root,context) == RET_END) {
		return RET_OK;
	}
	binary_tree_for_loop_inter(root->right, loop_fun,context);
	return RET_OK;
}
typedef struct _double_list_ {
	binary_tree_node_s *head;
	binary_tree_node_s*cur;
}double_list_s;

ret_e tree_node_convert(void *root,void *double_list) 
{
	double_list_s * dlist = (double_list_s *)double_list;
	binary_tree_node_s *node = (binary_tree_node_s*)root;

	if (dlist == NULL || node == NULL) {
		return RET_PRA;
	}

	node->left= dlist->cur;
	if (dlist->head == NULL) {
		dlist->head = node;
	} else {
		dlist->cur->right = node;
	}
	dlist->cur = node;	
	
	return RET_OK;
}
void dlist_for_loop(void*node,loop_func loop_fun)
{
	binary_tree_node_s *root = (binary_tree_node_s *)node;
	
	while (root != NULL) {
		loop_fun((root->data),NULL);
		root = root->right;
	}
}
void * tree_to_dlist(binary_tree_s*tree)
{
	double_list_s dlist = {NULL,NULL};
	
	binary_tree_for_loop_inter(tree->root,tree_node_convert,&dlist);
	return dlist.head;
}

void  binary_tree_mid_out_by_recursion(binary_tree_node_s *root,loop_func print_fun)
{
	if (root == NULL ||print_fun == NULL ) {
		return ;
	}
	if (root->left != NULL) {
		binary_tree_mid_out_by_recursion(root->left,print_fun);
	}
	print_fun(root->data,NULL);
	if (root->right != NULL) {
		binary_tree_mid_out_by_recursion(root->right,print_fun);
	}
}
int binary_tree_mid_out_by_non_recursion(binary_tree_node_s *root,loop_func print_fun,void **context)
{
	stack_s *stack;
	int i = 0;
	
	if (root == NULL ||print_fun == NULL ) {
		return 0;
	}
	stack = stack_create(0x0fff);
	stack_push(stack,root);
	while (root != NULL || (stack_is_empty(stack) == RET_OK)) {
		if (root != NULL) {
			root = root->left;
			if (root!= NULL) {
				stack_push(stack,(void *)root);
			}
		} else {
			stack_pop(stack,(void **)&root);
			print_fun(root->data,context+i);
			i++;
			root = root->right;
			if (root != NULL) {
				stack_push(stack,(void *)root);
			}
		}
	}
	stack_destory(stack);
	return i;
}

void  binary_tree_pre_out_by_recursion(binary_tree_node_s *root,loop_func print_fun)
{
	if (root == NULL ||print_fun == NULL ) {
		return ;
	}
	print_fun(root->data,NULL);
	if (root->left != NULL) {
		binary_tree_pre_out_by_recursion(root->left,print_fun);
	}
	if (root->right != NULL) {
		binary_tree_pre_out_by_recursion(root->right,print_fun);
	}
}
int binary_tree_pre_out_by_non_recursion(binary_tree_node_s *root,loop_func print_fun,void **context)
{
	stack_s *stack;
	int i = 0;

	if (root == NULL ||print_fun == NULL ) {
		return 0;
	}
	stack = stack_create(0x0fff);
	if (stack == NULL) {
		return 0;
	}
	stack_push(stack,root);
	while (root != NULL || (stack_is_empty(stack) == RET_OK)) {
		if (root != NULL) {
			print_fun(root->data,context+i);
			i++;
			root = root->left;
			if (root != NULL) {
				stack_push(stack,root);
			}
		} else {
			stack_pop(stack,(void **)&root);
			root = root ->right;
			if (root != NULL) {
				stack_push(stack,root);
			}
		}
	} 
	stack_destory(stack);
	return i;
}
void  binary_tree_last_out_by_recursion(binary_tree_node_s *root,loop_func print_fun)
{
	if (root == NULL ||print_fun == NULL ) {
		return ;
	}
	if (root->left != NULL) {
		binary_tree_last_out_by_recursion(root->left,print_fun);
	}
	if (root->right != NULL) {
		binary_tree_last_out_by_recursion(root->right,print_fun);
	}
	print_fun(root->data,NULL);
}
void  binary_tree_last_out_by_non_recursion(binary_tree_node_s *root,loop_func print_fun)
{
	stack_s *stack;
	
	if (root == NULL ||print_fun == NULL ) {
		return ;
	}
	stack = stack_create(0x0fff);
	if (stack == NULL) {
		return;
	}
	stack_push(stack,root);
	while (root != NULL || (stack_is_empty(stack) == RET_OK)) {
		if (root != NULL) {
			root = root->left;
			if (root != NULL) {
				stack_push(stack,root);
			}
		} else {
			stack_top(stack,(void **)&root);
			if (root ->right != NULL && !(root->data & 0x80000000)) {
				root->data |= 0x80000000;
				root = root ->right;
				stack_push(stack,root);
			} else {
				stack_pop(stack,(void **)&root);
				root->data = root->data & ~(0x80000000);
				print_fun(root->data,NULL);
				root = NULL;
			}
		}
	} 
	stack_destory(stack);
}
static int array_find(int *mid,int len,int data)
{
	int i;

	for (i=0; i<len; i++) {
		if (mid[i] == data) {
			break;
		}
	}
	return  i;
}
binary_tree_node_s * binary_tree_build_by_mid_and_pre(int *pre,int *mid,int len)
{
	int data = pre[0];
	int root_offset;
	binary_tree_node_s *root;
	
	root = binary_tree_node_create(data);
	root_offset = array_find(mid,len,data);
	if (root_offset != 0) {			/*exist left node*/
		root->left = binary_tree_build_by_mid_and_pre(pre+1,mid,root_offset);
	} 
	if (root_offset != len-1) { 		/*exist right node*/
		root->right = binary_tree_build_by_mid_and_pre(pre+1+root_offset,\
					mid+root_offset+1,len-root_offset-1); 
	}
	return root;
}

